public class test03 {
    class Solution {
        List<List<String>> res;
        List<String> list;
        public List<List<String>> partition(String s) {
            res = new ArrayList<>();
            list = new ArrayList<>();
            backTracking(s,0);
            return res;
        }
        private void backTracking(String s,int start){
            if(start==s.length()){
                res.add(new ArrayList(list));
                return;
            }
            for(int i = start;i<s.length();i++){
                if(isValid(s,start,i)){
                    list.add(s.substring(start,i+1));
                    backTracking(s,i+1);
                    list.removeLast();
                }
            }
        }
        //判断字符串是否回文
        private boolean isValid(String s,int begin,int end){
            for(int i = begin,j = end;i<j;i++,j--){
                if(s.charAt(i)!=s.charAt(j)){
                    return false;
                }
            }
            return true;
        }
    }
}
